package Leetcode.lc053;

/***
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 子数组是数组中的一个连续部分。
 */
public class Sloution {
    /***
     *  核心函数
     * @param nums
     * @return   最大和子数组，最优结构，动态规划
     *  转化问题为子问题，以nums[i]结尾的子数组的最大和，问题就简单很多
     *  但也得分情况，若nums[i]均大于0，那dp[i]=dp[i-1]+num[i]母庸质疑
     *  若前一个dp[i-1]<=0，那dp[i]=num[i]，这就是状态方程
     *  其中dp[i]为记忆数组，保存最大和，表示以num[i]结尾的最大和
     */
    public int maxSubArray(int[] nums) {
        //构建记忆数组
        int[] dp=new int[nums.length];
        //结果
        int res=nums[0];
        //初始化第一位
        dp[0]=nums[0];
        //遍历+使用状态转移方程
        for (int i=1;i<nums.length;i++){
            if(dp[i-1]>0){
                dp[i]=dp[i-1]+nums[i];
            }else{
                dp[i]=nums[i];
            }
            res=Math.max(res,dp[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        Sloution sloution = new Sloution();
        int[] test={-1,1,2,3,4,5};
        int i = sloution.maxSubArray(test);
        System.out.print(i);

    }
}
